In concurrent computer systems, race conditions may occur when multiple concurrent processes update the same or related memory locations simultaneously. Race conditions leave the memory state inconsistent relative to software requirements. For example, if two processes add entries to a software data structure such as a hash table simultaneously, both mapping to the same hash bucket, the result may be a corrupted linked list in that hash bucket.
One well-known approach to solve the race condition problem is to use locks. A process is required to acquire the lock before modifying the data structure and release the lock afterwards. An atomic test-and-set instruction is sometimes supported in hardware. Problems associated with locking include deadlock, priority inversion, and extra overhead of queuing on locks. Some conventional approaches such as non-blocking synchronization (NBS) and hardware transactional memory (HTM) systems address certain problems associated with locking, but other issues remain, including high memory overhead and operational inefficiencies due to conflicting access.